//==================================================================
//  Copyright (C) 2006  Davide Pasca
//
//  This library is free software; you can redistribute it and/or
//  modify it under the terms of the GNU Lesser General Public
//  License as published by the Free Software Foundation; either
//  version 2.1 of the License, or (at your option) any later version.
//
//  This library is distributed in the hope that it will be useful,
//  but WITHOUT ANY WARRANTY; without even the implied warranty of
//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
//  Lesser General Public License for more details.
//
//  You should have received a copy of the GNU Lesser General Public
//  License along with this library; if not, write to the Free Software
//  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
//==================================================================
//==
//==
//==
//==
//==================================================================

#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

#include "m5d_tvert.h"
#include "m5d_utils_ext.h"
#include "m5d_mesh.h"
#include "m5d_scene.h"

//==================================================================
using namespace M5D;

//==================================================================
typedef struct
{
	u_int	mask;
	int		idx;
} sitem_t;

//==================================================================
void Mesh::remapVertsInTriangles( VType::VType type_idx, const std::vector<int> &idx_trans_table )
{
#ifdef _DEBUG
	MultiVerts			&verts = _geomp->GetVerts();

	int	nv;
	switch ( type_idx )
	{
	case VType::POS: nv = verts.GetPosN(); break;
	case VType::TEX: nv = verts.GetTexN(); break;
	case VType::COL: nv = verts.GetColN(); break;
	case VType::NOR: nv = verts.GetNorN(); break;
	}
#endif

	Triangles	&trigs = _geomp->GetTrigs();

	// adjust the triangles
	for (triangle_iter tp = trigs._list.begin(); tp != trigs._list.end(); ++tp)
	{
		for (int j=0; j < 3; ++j)
		{
			int	*p = &tp->idx[type_idx][j];

			PASSERT( *p >= 0 );
#ifdef _DEBUG
			PASSERT( idx_trans_table[ *p ] >= 0 && idx_trans_table[ *p ] < nv );
#endif

			*p = idx_trans_table[ *p ];
		}
	}
}

//==================================================================
void Mesh::OptimizeVerts( VType::VType type_idx )
{
	if ( type_idx != VType::NONE )
	{
		msh_weld( type_idx, 0.0f );
	}
	else
	{
		for (int i=0; i < VType::N; ++i)
			msh_weld( (VType::VType)i, 0.0f );
	}
}

//==================================================================
//== SIMPLIFICATION
//==================================================================
void Mesh::killUnusedPosVerts() throw(...)
{
	int		i, compact_idx;
	Vector3	*svrtp, *dvrtp;
	float	*sweip, *dweip;
	u_char	*sbnip, *dbnip;
	int		n_verts;

	MultiVerts		&verts = _geomp->GetVerts();
	Triangles		&trigs = _geomp->GetTrigs();
	verts.LockRW( __FILE__, __LINE__ );
	trigs.LockRW( __FILE__, __LINE__ );

	n_verts = verts.GetPosN();
	if ( n_verts <= 0 )
		return;

	std::vector<int>	trans_map( n_verts );
	std::vector<bool>	used_mapp( n_verts, false );

	// switch on the points correspondent to the vertices that are still being used
	for (triangle_coiter tp=trigs._list.begin(); tp != trigs._list.end(); ++tp)
	{
		used_mapp[ tp->pos[0] ] = true;
		used_mapp[ tp->pos[1] ] = true;
		used_mapp[ tp->pos[2] ] = true;
	}

	// create a translation map from full vertices into compact vertices
	// also compacts the vertices

	sweip = dweip = verts.GetWeiW();
	sbnip = dbnip = verts.GetBNLW();
	svrtp = dvrtp = verts.GetPosW();

	PASSERT( svrtp != NULL );

	compact_idx = 0;
	for (i=0; i < n_verts; ++i)
	{
		if ( used_mapp[i] )
		{
			if ( sbnip )
				memcpy( dbnip, sbnip, verts.GetWeightsMax() * sizeof(*dbnip) );

			if ( sweip )
				memcpy( dweip, sweip, verts.GetWeightsMax() * sizeof(*dweip) );

			dvrtp[0] = svrtp[0];

			dbnip += verts.GetWeightsMax();
			dweip += verts.GetWeightsMax();
			dvrtp += 1;

			trans_map[i] = compact_idx++;
		}
		else
		{
			trans_map[i] = -1;
		}
		if ( sbnip )	sbnip += verts.GetWeightsMax();		
		if ( sweip )	sweip += verts.GetWeightsMax();
		svrtp += 1;
	}
	verts.SetPosN( compact_idx );

	verts.Unlock();
	trigs.Unlock();

	// finally remap the triangles and strips to use the compact vertices
	remapVertsInTriangles( VType::POS, trans_map );
}

//==================================================================
void Mesh::eliminateUnusedVerts( VType::VType type_idx )
{
int		i, compact_idx;
u_char	*svrtp, *dvrtp;
int		vsize;
int		n_verts;

	PASSERT( type_idx >= 0 && type_idx < VType::N );

	MultiVerts		&verts = _geomp->GetVerts();
	Triangles		&trigs = _geomp->GetTrigs();
	verts.LockRW( __FILE__, __LINE__ );
	trigs.LockRW( __FILE__, __LINE__ );

	switch ( type_idx )
	{
	case VType::POS:
		killUnusedPosVerts();
		return;

	case VType::TEX: n_verts = verts.GetTexN(); vsize = sizeof(*verts.GetTexW()); break;
	case VType::COL: n_verts = verts.GetColN(); vsize = sizeof(*verts.GetColW()); break;
	case VType::NOR: n_verts = verts.GetNorN(); vsize = sizeof(*verts.GetNorW()); break;
	}

	if ( n_verts <= 0 )
		return;

	std::vector<int>	trans_map( n_verts );
	std::vector<bool>	used_mapp( n_verts, false );

	//------------------------------------------------
	// switch on the points correspondent to the vertices that are still being used
	for (triangle_coiter tp=trigs._list.begin(); tp != trigs._list.end(); ++tp)
	{
		used_mapp[ tp->idx[type_idx][0] ] = true;
		used_mapp[ tp->idx[type_idx][1] ] = true;
		used_mapp[ tp->idx[type_idx][2] ] = true;
	}

	//------------------------------------------------
	// create a translation map from full vertices into compact vertices
	// also compacts the vertices
	switch ( type_idx )
	{
	case VType::TEX: svrtp = dvrtp = (u_char *)verts.GetTexW(); break;
	case VType::COL: svrtp = dvrtp = (u_char *)verts.GetColW(); break;
	case VType::NOR: svrtp = dvrtp = (u_char *)verts.GetNorW(); break;
	}

	PASSERT( svrtp != NULL );
	compact_idx = 0;
	for (i=0; i < n_verts; ++i)
	{
		if ( used_mapp[i] )
		{
			memcpy( dvrtp, svrtp, vsize );
			dvrtp += vsize;
			trans_map[i] = compact_idx++;
		}
		else
			trans_map[i] = -1;

		svrtp += vsize;
	}

	//------------------------------------------------
	switch ( type_idx )
	{
	case VType::TEX:
			// set the new vertex count
			verts.SetTexN( compact_idx );
			break;

	case VType::COL:
			// set the new vertex count
			verts.SetColN( compact_idx );
			break;

	case VType::NOR:
			// set the new vertex count
			verts.SetNorN( compact_idx );
			break;
	}

	verts.Unlock();
	trigs.Unlock();

	// finally remap the triangles and strips to use the compact vertices
	remapVertsInTriangles( type_idx, trans_map );
}

//==================================================================
void Mesh::eliminateBadTrigs( u_int range_begin, u_int range_end )
{
	Triangles		&trigs = _geomp->GetTrigs();

	if ( range_end == 0 )
		range_end = trigs._list.size();

	trigs.LockRW( __FILE__, __LINE__ );

	// only copy valid triangles	
	Triangle	*a = &trigs._list.at( range_begin );
	Triangle	*b = &trigs._list.at( range_begin );
	Triangle	*endp = &trigs._list.at( range_end-1 );

	while ( b <= endp )
	{
		if ( b->IsValid() )
			*a++ = *b;

		++b;
	}
	trigs._list.resize( a - &trigs._list.front() );

	trigs.Unlock();

	// removed a position vertex range check here.. ummm ok be safe but this check
	// here is really out of place
}

//==================================================================
//== NORMALS
//==================================================================
static int is_bad_normal( float *n )
{
float	m;

	m = (float)sqrt( n[0]*n[0] + n[1]*n[1] + n[2]*n[2] );
	if ( m < 0.8f )
		return 1;

	return 0;
}

//==================================================================
void Mesh::calcTrigsNormals()
{
	MultiVerts		&verts = _geomp->GetVerts();
	Triangles		&trigs = _geomp->GetTrigs();
	verts.LockR( __FILE__, __LINE__ );
	trigs.LockRW( __FILE__, __LINE__ );

	const Vector3	*base_posp = ((const MultiVerts &)verts).GetPosR();

	for (triangle_iter tp=trigs._list.begin(); tp != trigs._list.end(); ++tp)
	{
		PASSERT( tp->pos[0] >= 0 && tp->pos[0] < verts._pos_vertsp.size() );
		PASSERT( tp->pos[1] >= 0 && tp->pos[1] < verts._pos_vertsp.size() );
		PASSERT( tp->pos[2] >= 0 && tp->pos[2] < verts._pos_vertsp.size() );

		const Vector3	&v1 = base_posp[ tp->pos[0] ];
		const Vector3	&v3 = base_posp[ tp->pos[1] ];
		const Vector3	&v2 = base_posp[ tp->pos[2] ];
		const Vector3	norm = (v1 - v2).GetCross(v3 - v2).GetNormalized();

		tp->tplane = Vector4( norm, -norm.GetDot( v1 ) );

		//PASSERT( !is_bad_normal( tp->tplane._v ) );
	}

	verts.Unlock();
	trigs.Unlock();
}

//==================================================================
void Mesh::calcVertsNormals( bool smooth )
{
	int		a, b, c;

	MultiVerts		&verts = _geomp->GetVerts();
	Triangles		&trigs = _geomp->GetTrigs();
	verts.LockRW( __FILE__, __LINE__ );
	trigs.LockR( __FILE__, __LINE__ );

	if NOT( smooth )
	{
		// if not smooth.. then generate one normal per triangle and assign them by
		// copying the tplane form the triangle itself

		int	nt = trigs._list.size();

		// make sure the normals are allocated
		verts.SetNorN( nt );
		Vector3	*vnormsp = verts.GetNorW();

		Triangle	*trip = &trigs._list.front();
		for (int i=0; i < nt; ++i, ++trip)
		{
			trip->nor[0] = trip->nor[1] = trip->nor[2] = i;

			Vector3	nor( trip->tplane.GetVector3() );

			vnormsp[ i ] = nor;
			vnormsp[ i ] = nor;
			vnormsp[ i ] = nor;
		}
		verts.Unlock();
		trigs.Unlock();
		return;
	}

	if ( verts.GetPosN() <= 0 )
	{
		verts.Unlock();
		trigs.Unlock();
		return;	// ehh !
	}

	//----------------------------------------------------------------------
	int		nvn = verts.GetNorN();
	Vector3	*vnp = verts.GetNorW();

	if ( nvn <= 0 || !vnp )
	{
		vnp = verts.AddNorN( verts.GetPosN() );
		nvn = verts.GetNorN();

		for (triangle_iter tp=trigs._list.begin(); tp < trigs._list.end(); ++tp)
		{
			tp->nor[0] = tp->pos[0];
			tp->nor[1] = tp->pos[1];
			tp->nor[2] = tp->pos[2];
		}
	}

	memset( vnp, 0, nvn * sizeof(*verts.GetNorW()) );

	// calc vertex normals
	for (triangle_coiter tp=trigs._list.begin(); tp < trigs._list.end(); ++tp)
	{
		Vector3	tri_nor = *(Vector3 *)&tp->tplane;

		a = tp->nor[0];	PASSERT( a >= 0 && a < nvn );
		b = tp->nor[1];	PASSERT( b >= 0 && b < nvn );
		c = tp->nor[2];	PASSERT( c >= 0 && c < nvn );

		vnp[a] += tri_nor;
		vnp[b] += tri_nor;
		vnp[c] += tri_nor;
	}

	vnp = verts.GetNorW();
	for (int i=nvn; i; --i, ++vnp)
	{
		vnp[0] = vnp[0].GetNormalized();
	}

	verts.Unlock();
	trigs.Unlock();
}

//==================================================================
void Mesh::remapMaterials( const int *mat_idx_trans_tablep )
{
	PASSERT( 0 );	// should implement the scene arrays serial idx instead (field inside a class)
/*	triangle_t	*trip = &trigs._list.front();
	for (int i=trigs._list.size(); i; --i, ++trip)
		trip->mate_id = mat_idx_trans_tablep[ trip->mate_id ];
*/
}

//==================================================================
//==================================================================
//=== EDGE STUFF BEGINS
//==================================================================
//==================================================================
struct edge_t
{
	int	faces[2];
	int	verts[2];
	edge_t(){}
};

typedef struct
{
	std::vector<edge_t>	edgesp;
} edge_list_t;

//==================================================================
static void el_init( edge_list_t *elp, int alloc_start )
{
	elp->edgesp.resize(0);
	//elp->edgesp.hint_expand( alloc_start );
}
//==================================================================
static void el_free( edge_list_t *elp )
{
	elp->edgesp.clear();
}
//==================================================================
static int el_add( edge_list_t *elp, int f1, int f2, int v1, int v2 )
{
	edge_t	e;
	e.faces[0] = f1;
	e.faces[1] = f2;
	e.verts[0] = v1;
	e.verts[1] = v2;
	elp->edgesp.push_back( e );
	
	return POK;
}
//==================================================================
static bool are_verts_shared( Triangle *trip, int va, int vb )
{
	PASSERT( va != vb );

	int cnt = 0;
	for (int i=0; i < 3; ++i)
		if ( trip[0][i] == va || trip[0][i] == vb ) ++cnt;

	if ( cnt == 2 )
		return true;

	return false;
}
/*
//==================================================================
static int are_trigs_hard_edged( const float *tn1p, const float *tn2p, float base_hard_cosa )
{
	float cosa = tn1p[0] * tn2p[0] + tn1p[1] * tn2p[1] + tn1p[2] * tn2p[2];

	//if ( cosa < 0 )	cosa = -cosa;

	if ( cosa < base_hard_cosa )
		return 1;

	return KOK;
}
*/
//==================================================================
static float triangles_match( const float *tn1p, const float *tn2p )
{
	return tn1p[0] * tn2p[0] + tn1p[1] * tn2p[1] + tn1p[2] * tn2p[2];

	//return -(cosa - min_required_cosa);
}

//==================================================================
struct tri_mesh_t
{
	static const int	MAX_TRIS = 128;

	int		tri_n;
	int		tri_idxs[MAX_TRIS];

	//----------------------------------------
	tri_mesh_t()
	{
		tri_n = 0;
	}
	//----------------------------------------
	void init()
	{
		tri_n = 0;
	}
	//----------------------------------------
	float min_match_in_group( int in_idx, Triangle *trigsp )
	{
	float	min_match, cur_match;

		min_match = 10000;
		const Vector4	&in_idx_tplane = trigsp[ in_idx ].tplane;

		for (int i=0; i < tri_n; ++i)
		{
			int	j = tri_idxs[i];

			cur_match = triangles_match( trigsp[ j ].tplane._v, in_idx_tplane._v );
			if ( cur_match < min_match )
				min_match = cur_match;
		}

		return min_match;
	}
	//----------------------------------------
	void add( int newidx )
	{
		PASSERT( tri_n < MAX_TRIS );
		tri_idxs[ tri_n++ ] = newidx;
	}
	//----------------------------------------
	void replace_nor_vidx( int old_vidx, int new_vidx, Triangle *trigsp )
	{
		for (int i=0; i < tri_n; ++i)
		{
			Triangle *trip = &trigsp[ tri_idxs[i] ];

			if ( trip->nor[0] == old_vidx )	trip->nor[0] = new_vidx;
			if ( trip->nor[1] == old_vidx )	trip->nor[1] = new_vidx;
			if ( trip->nor[2] == old_vidx )	trip->nor[2] = new_vidx;
		}
	}
};

//==================================================================
void Mesh::UnshareVertsByNormalAngle( float base_hard_angle )
{
	float	base_hard_cosa;

	MultiVerts		&verts = _geomp->GetVerts();
	Triangles		&trigs = _geomp->GetTrigs();

	if ( verts.GetPosN() < 3 )
		return;

	verts.LockRW( __FILE__, __LINE__ );
	trigs.LockRW( __FILE__, __LINE__ );

	base_hard_cosa = cosf( base_hard_angle * 3.14159265f / 180 );

	// ..just to be safe
	calcTrigsNormals();

	// create the triangles-in-vert structure
	TriIdx_VertIdx	tidx_vidx( _geomp );

	try {
	int		nv = tidx_vidx.len();
	// make sure we have all matching
	if ( nv != verts.GetPosN() )
	{
		PASSERT( 0 );
		throw "Bad things";
	}

	// initially set the number of normal vertices to the number of pos vertices
	// ..the number will eventually grow.. (could be possibly less ? Maybe we take care
	// of that in a later stage, reducing normals with brute force)
	verts.SetNorN( nv );
	for (triangle_iter tp=trigs._list.begin(); tp != trigs._list.end(); ++tp)
	{
		tp->nor[0] = tp->pos[0];
		tp->nor[1] = tp->pos[1];
		tp->nor[2] = tp->pos[2];
	}

	tri_mesh_t	*tri_groups = new tri_mesh_t[256];
	int			tri_groups_n;

	for (int vidx=0; vidx < nv; ++vidx)
	{
		TriList	&trilist = tidx_vidx[ vidx ];

		if ( trilist.len() > 256 )
		{
			delete [] tri_groups;
			PASSERT( 0 );
			throw;
		}

		tri_groups_n = 0;
		for (int j=0; j < trilist.len(); ++j)
		{
			int			tidx = trilist[ j ];
			float		best_match_cosa;
			int			best_match_gr_idx;

			best_match_cosa = base_hard_cosa;
			best_match_gr_idx = -1;
			for (int k=0; k < tri_groups_n; ++k)
			{
				float t = tri_groups[ k ].min_match_in_group( tidx, &trigs._list.front() );
				if ( t > best_match_cosa )
				{
					best_match_cosa = t;
					best_match_gr_idx = k;
				}
			}

			// add into a new group if wasn't added
			if ( best_match_gr_idx >= 0 )
			{
				//PASSERT( best_match_cosa >= base_hard_cosa );	// unless i'm very much mistaken...
				tri_groups[ best_match_gr_idx ].add( tidx );
			}
			else
			{
				PASSERT( tri_groups_n < 256 );
				tri_groups[ tri_groups_n ].init();
				tri_groups[ tri_groups_n ].add( tidx );
				++tri_groups_n;
			}
		}

		// if there is only one group, then it means that we don't need to clone the vertex
		if ( tri_groups_n > 1 )
		{
			// ..otherwise.. make additional tri_groups_n-1 vertices

			// this is the new new normal vertex index
			int	first_new_nor_vidx = verts.GetNorN();

			// now we add a new normal vertices
			verts.AddNorN( tri_groups_n-1 );

			// the original vertex stay for the first group
			// ..the new vertices are assigned one for each group,
			// starting from the group 1 (2nd one)
			for (int i=1; i < tri_groups_n; ++i)
			{
				// replace vidx with the new vert
				// no need to update the tidx_vidx, because we aren't going to parse
				// this vert's trilist again..
				tri_groups[ i ].replace_nor_vidx( vidx, first_new_nor_vidx + (i-1), &trigs._list.front() );
			}
		}
	}

	delete [] tri_groups;

	} catch(...) {
		verts.Unlock();
		trigs.Unlock();

		throw "woooooo !";
	}

	verts.Unlock();
	trigs.Unlock();

	// FIRST !!! ...recalc new normals, then worry about optimizing.. geez
	calcVertsNormals( true );
	OptimizeVerts( VType::NOR );
}
/*
//==================================================================
void Mesh::UpdateDispList() throw(...)
{
	_geomp->UpdateDispLists( _scenep );
}
*/